package com.moyoutian.cscn;


import com.moyoutian.utils.ArrayUtils;

import java.util.Arrays;

/**
 * 背景：投票选举村干部
 * 假设本村不的人不重名。一人有一票的投票权，可以投自己或者他人。现在每个人都已经投票完毕。并且这些票已经收集到大队（村干部的票被收集到了一个数组里）。需要选出一个被投了票数超过一半的人。怎么选呢？请你给出答案。伪代码即可。
 * <p>
 * 条件一组
 * 额外的空间复杂度O(n)
 * 时间复杂度：O(1)
 * 提示：可以使用集合数组链表等结构
 * 条件二组
 * 空间复杂度O(1),不可借用集合链表等结构
 * 时间复杂度O(1)
 * 提示
 * 第二组条件相信大家应该都有想法并且能够实现，比如借助hashMap等就是利用集合并计数。
 * <p>
 * 第二组呢就有些难度了，大家要关注超过一半这个关键性的要
 */
public class Demo1 {

    public static void main(String[] args) {

        //初始化投票 随机数组 人名就暂定为数字编号 ,参数1数组长度，参数2，随机数的最大值
        int[] names = ArrayUtils.getIntAr(5, 2);
        System.out.println(Arrays.toString(Arrays.stream(names).toArray()));
        int name = getName(names);
        if (name == -1) {
            System.out.println("没有候选者");
        } else {
            System.out.println("候选者为：" + name);
        }

    }


    /**
     * 第二组实现
     *
     * @param ints 候选人数组
     */
    public static int getName(int[] ints) {
        //候选者编号
        int p = -1;
        // 血量
        int ph = 0;
        // 先便利一遍数组
        for (int i = 0; i < ints.length; i++) {
            //如果血量为0，当前值变为候选者,血量+1
            if (ph == 0) {
                p = ints[i];
                ph++;
            } else if (p == ints[i]) {
                //如果血量为不为0，当前值变等于候选者,血量+1
                ph++;
            } else {
                //如果血量为不为0，当前值变等于候选者,血量-1
                ph--;
            }
        }
        // 在便利一变数据确定候选者的数量是否大于数组长度的一半
        if (p != -1) {
            //重置血量
            ph = 0;
            for (int i = 0; i < ints.length; i++) {
                if (p == ints[i]) {
                    ph++;
                }
            }

            if (ph > ints.length / 2) {
                return p;
            }
        }
        return -1;
    }
}
